package ljl.alg.wangzheng_camp.round1.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 * fib 小小的变种
 * 可以说是很猥琐了
 * */
public class _08_01_3_step {
    
    /**
     * 不是 1 或 2，而是 1 2 或 3！
     * 好题， 好题！
     *
     * 王八蛋写了递归，用递归却超时
     * 我记忆化搜索了那就
     *
     * 操记忆化搜索也这么慢？
     * */
    Map<Integer, Integer> cache = new HashMap<>();
    public int waysToStep(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        if (cache.containsKey(n)) return cache.get(n);
        int res = ((waysToStep(n - 1) + waysToStep(n - 2))%1000000007 + waysToStep(n - 3))%1000000007;
        cache.put(n, res);
        return res;
    }
    
    /**
     * 看来是时候祭出我的 dp 了
     * 蒙对了，怎么还是这么慢？
     * */
    public int waysToStep2(int n) {
        if (n <= 2) return n;
        if (n == 3) return 4;
        // 只跟最近三个变量有关所以声明 abc
        int a = 1, b = 2, c = 4;
        while (n-- > 3) {
            int t = a;
            a = b;
            b = c;
            c = ((a + b) % 1000000007 + t) % 1000000007;
        }
        return c;
    }
}
